#include "heap.h"

//int main()
//{
//  Heap hp;
//  HeapInit(&hp);
//  int a[] = {32,10,50,60,100,65};
//  for(size_t i =0; i<sizeof(a)/sizeof(int); i++){
//    HeapPush(&hp,a[i]);
//  }
//  HeapPrint(&hp);
//
//  int i =0;
//  while(!HeapEmpty(&hp)){
//    std::cout << HeapTop(&hp) << " ";
//    HeapPop(&hp);
//  }
//  std:: cout <<std::endl;
//
//
//  HeapDestroy(&hp);
//  return 0;
//}

void HeapSort(int* a, int n)
{
  //向上调整 O(n*logn)
//  for(size_t i =1; i<n; i++){
//    AdjustUp(a,i);
//  }
//
  //向下调整 O(n)
  for(int i = (n-2)/2; i>=0; i--){
    AdjustDown(a,n,i);
  }

  //时间复杂度O(N*logN)
  int end = n-1;
  while(end > 0){
    Swap(&a[0],&a[end]);
    AdjustDown(a,end,0);
    --end;
  }
}

void PrintTopK(const char* filename,int k)
{
  FILE* fout = fopen(filename,"r");
  if(fout == NULL){
    perror("fopen fail");
    exit(-1);
  }

  int* minHeap = (int*)malloc(sizeof(int)*k);
  if(minHeap == NULL){
    perror("malloc fail");
    exit(-1);
  }

  for(int i =0; i<k; i++){
    fscanf(fout,"%d",&minHeap[i]);
  }

  for(int i = (k-2)/2; i>=0; i++){
    AdjustDown(minHeap,k,0);
  }

  int x =0;
  while(fscanf(fout,"%d",&x)!= EOF){
    if(x > minHeap[0]){
      minHeap[0] = x;
      AdjustDown(minHeap,k,0);
    }
  }

  for(int i =0; i<k; i++){
    std::cout << minHeap[i] << " ";
  }
  std::cout << std::endl;
}

void CreateDate()
{
  int n =10000;
  srand(time(0));
  const char* file = "data.txt";
  FILE* fin = fopen(file,"w");
  if(fin == NULL){
    perror("fopen fail");
    exit(-1);
  }

  for(size_t i =0; i<n; i++){
    int x = rand() % 1000000;
    fprintf(fin,"%d\n",x);
  }
}

//int main()
//{
//
//  int a[] = {2,3,5,7,4,6,8,65,100,70,32};
//  HeapSort(a,sizeof(a)/sizeof(int));
//
//  for(size_t i = 0; i<sizeof(a)/sizeof(int); i++){
//    std::cout<< a[i] <<" ";
//  }
//  std::cout<< std::endl;
//
//  //std::cout<< sizeof(size_t) <<std:: endl;
//  return 0;
//}


int main()
{
  PrintTopK("data.txt",5);
  return 0;
}
